{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest Subarray with Sum at Least K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #queue #array #binary-search #prefix-sum #sliding-window #monotonic-queue #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #队列 #数组 #二分查找 #前缀和 #滑动窗口 #单调队列 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shortestSubarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #和至少为 K 的最短子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和一个整数 <code>k</code> ，找出 <code>nums</code> 中和至少为 <code>k</code> 的 <strong>最短非空子数组</strong> ，并返回该子数组的长度。如果不存在这样的 <strong>子数组</strong> ，返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p><strong>子数组</strong> 是数组中 <strong>连续</strong> 的一部分。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1], k = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2], k = 4\n",
    "<strong>输出：</strong>-1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,-1,2], k = 3\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-subarray-with-sum-at-least-k](https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-subarray-with-sum-at-least-k](https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1]\\n1', '[1,2]\\n4', '[2,-1,2]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def shortestSubarray(self, A, K):\n",
    "        N = len(A)\n",
    "        P = [0]\n",
    "        for x in A:\n",
    "            P.append(P[-1] + x)\n",
    "\n",
    "        #Want smallest y-x with Py - Px >= K\n",
    "        ans = N+1 # N+1 is impossible\n",
    "        monoq = collections.deque() #opt(y) candidates, represented as indices of P\n",
    "        for y, Py in enumerate(P):\n",
    "            #Want opt(y) = largest x with Px <= Py - K\n",
    "            while monoq and Py <= P[monoq[-1]]:\n",
    "                monoq.pop()\n",
    "\n",
    "            while monoq and Py - P[monoq[0]] >= K:\n",
    "                ans = min(ans, y - monoq.popleft())\n",
    "\n",
    "            monoq.append(y)\n",
    "\n",
    "        return ans if ans < N+1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, A: list, K: int) -> int:\n",
    "        if not A:\n",
    "            return -1\n",
    "        sum_val = 0\n",
    "        left_idx = 0\n",
    "        len_A = len(A)\n",
    "        min_len_val = len_A + 1\n",
    "        for i in range(len_A):\n",
    "            sum_val += A[i]\n",
    "            if sum_val <= 0:\n",
    "                sum_val = 0\n",
    "                left_idx = i + 1\n",
    "                continue\n",
    "\n",
    "            j = i\n",
    "            while A[j] < 0:\n",
    "                A[j - 1], A[j] = A[j - 1] + A[j], 0\n",
    "                j -= 1\n",
    "\n",
    "            if sum_val >= K:\n",
    "                while left_idx < i:\n",
    "                    if sum_val - A[left_idx] >= K:\n",
    "                        sum_val -= A[left_idx]\n",
    "                        left_idx += 1\n",
    "                        continue\n",
    "                    break\n",
    "                len_val = i - left_idx + 1\n",
    "                if len_val < min_len_val:\n",
    "                    min_len_val = len_val\n",
    "                    if min_len_val <= 1:\n",
    "                        return min_len_val\n",
    "        return min_len_val if min_len_val <= len_A else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_max(self, x:List[int], st: int) -> int:\n",
    "        dif = 0\n",
    "        top = 0\n",
    "        for n in range(st,len(x)):\n",
    "            dif += x[n]-x[n-st]\n",
    "            if dif > top:\n",
    "                top = dif\n",
    "        return top\n",
    "    \n",
    "    def shortestSubarray(self, A: List[int], K: int) -> int:\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :type K: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l = len(A)\n",
    "        ma = max(A)\n",
    "        if ma >= K:\n",
    "            return 1\n",
    "        else:\n",
    "            n = max(K//ma,1)\n",
    "            mx = sum(A[:n-1])+self.get_max(A,n-1)\n",
    "            if l >= 10000:\n",
    "                while K-mx > ma:\n",
    "                    n += max((K-mx)/ma,1)\n",
    "                    n = int(n//1)\n",
    "                    mx = sum(A[:n-1])+self.get_max(A,n-1)\n",
    "        while sum(A[:n-1])+self.get_max(A,n-1) < K:\n",
    "            if n <= l:\n",
    "                n += 1\n",
    "            else:\n",
    "                n = 0\n",
    "                break\n",
    "        return n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_max(self, x:List[int], st: int) -> int:\n",
    "        dif = 0\n",
    "        top = 0\n",
    "        for n in range(st,len(x)):\n",
    "            dif += x[n]-x[n-st]\n",
    "            if dif > top:\n",
    "                top = dif\n",
    "        return top\n",
    "    \n",
    "    def shortestSubarray(self, A: List[int], K: int) -> int:\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :type K: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l = len(A)\n",
    "        ma = max(A)\n",
    "        if ma >= K:\n",
    "            return 1\n",
    "        else:\n",
    "            n = max(K//ma,1)\n",
    "            mx = sum(A[:n-1])+self.get_max(A,n-1)\n",
    "            if l >= 10000:\n",
    "                while K-mx > ma:\n",
    "                    n += max((K-mx)/ma,1)\n",
    "                    n = int(n//1)\n",
    "                    mx = sum(A[:n-1])+self.get_max(A,n-1)\n",
    "        while sum(A[:n-1])+self.get_max(A,n-1) < K:\n",
    "            if n <= l:\n",
    "                n += 1\n",
    "            else:\n",
    "                n = 0\n",
    "                break\n",
    "        return n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def shortestSubarray(self, A: List[int], K: int) -> int:\n",
    "        N = len(A)\n",
    "        res = N + 1\n",
    "        a = [0] * res\n",
    "        for i in range(N):\n",
    "            a[i+1] = a[i]+A[i]\n",
    "                \n",
    "        d = deque()\n",
    "        for i in range(N+1):\n",
    "            while len(d) != 0 and a[i] - a[d[0]] >= K:\n",
    "                res = min(res,i - d.popleft())\n",
    "            while len(d) != 0 and a[i] <= a[d[-1]]:\n",
    "                d.pop()\n",
    "            d.append(i)\n",
    "        \n",
    "        if res <= N:\n",
    "            return res\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, A: List[int], K: int) -> int:\n",
    "        # 累加和数组\n",
    "        sum_ = [0] * (len(A)+1)\n",
    "        for i in range(len(A)):\n",
    "            if i == 0:\n",
    "                sum_[i+1] = A[0]\n",
    "            else:\n",
    "                sum_[i+1] = sum_[i] + A[i]\n",
    "        # 找sum_[y] - sum_[x] >= K的最小的y-x\n",
    "        # 递增队列\n",
    "        queue = [0]\n",
    "        ans = len(A)+1\n",
    "        for j in range(1,len(A)+1):\n",
    "            while len(queue) > 0 and sum_[queue[-1]] >= sum_[j]:\n",
    "                queue.pop()\n",
    "            queue.append(j)\n",
    "            while len(queue) > 1 and sum_[queue[-1]] - sum_[queue[0]] >= K:\n",
    "                tmp = queue.pop(0)\n",
    "                ans = min(queue[-1] - tmp,ans)\n",
    "        return ans if ans < len(A) + 1 else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, A: List[int], K: int) -> int:\n",
    "        res, s, begin = -1, 0, 0\n",
    "        for i in range(len(A)):\n",
    "            if A[i] >= K:\n",
    "                return 1\n",
    "            s += A[i]\n",
    "            if s <= 0:\n",
    "                begin, s = i+1, 0\n",
    "                continue\n",
    "            j = i - 1\n",
    "            while j >= 0 and A[j+1] < 0:\n",
    "                A[j] = A[j+1] + A[j]\n",
    "                A[j+1] = 0\n",
    "                j -= 1\n",
    "            if s >= K:\n",
    "                while s - A[begin] >= K or A[begin] <= 0:\n",
    "                    s -= A[begin]\n",
    "                    begin += 1\n",
    "                if res < 0 or res > i - begin + 1:\n",
    "                    res = i - begin + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        # 理解题意！“返回A的最短的非空连续子数组的长度，该子数组的和至少为K。”\n",
    "        # 和只要和大于k即可，如[2,-1,2,3]，K=1，答案是1(第一个数字2就可以满足)，不是2(前两个元素2-1恰好等于1)...\n",
    "        n = len(nums)\n",
    "        for i in range(1, n): # 原地更新A，用于存储累计和，[2,-1,2,3] -> [2, 1, 3, 6]\n",
    "            nums[i] += nums[i - 1]\n",
    "        nums = [0] + nums # 首位加一个0，便于后续比较num < A[index_list[-1]]时做出队操作\n",
    "\n",
    "        res = n + 1 # 初始化res\n",
    "        index_list = collections.deque() # 使用双端队列存储新A数组(累计和)中元素的下标\n",
    "        for i, num in enumerate(nums):\n",
    "            # 如累计和num小于队列当前位置对应的累计和，说明原数组A中是一个负值元素。\n",
    "            # 题意是只要和大于K即可，所以，忽略负值元素，pop\n",
    "            while index_list and num < nums[index_list[-1]]:\n",
    "                index_list.pop()\n",
    "            # 当num - A[index_list[0]]满足要求时，记录下当前i值与index_list中最小的索引的差值，和原res比较出最小值\n",
    "            while index_list and num - nums[index_list[0]] >= k:\n",
    "                res = min(res, i - index_list.popleft())\n",
    "            index_list.append(i)  # 依次把i压入index_list中\n",
    "\n",
    "        return res if res < n + 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 862.和至少为K的最短子数组\n",
    "# 返回A的最短的非空连续子数组的长度，该子数组的和至少为K 。\n",
    "#\n",
    "# 如果没有和至少为K的非空子数组，返回 - 1 。\n",
    "#\n",
    "# 示例1：\n",
    "# 输入：A = [1], K = 1\n",
    "# 输出：1\n",
    "#\n",
    "# 示例2：\n",
    "# 输入：A = [1, 2], K = 4\n",
    "# 输出：-1\n",
    "#\n",
    "# 示例3：\n",
    "# 输入：A = [2, -1, 2], K = 3\n",
    "# 输出：3\n",
    "#\n",
    "# 提示：\n",
    "#\n",
    "# 1 <= A.length <= 50000\n",
    "# -10 ^ 5 <= A[i] <= 10 ^ 5\n",
    "# 1 <= K <= 10 ^ 9\n",
    "from typing import List\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "#         if not nums:\n",
    "#             return -1\n",
    "#\n",
    "#         left = right = 0\n",
    "#         res = float('inf')\n",
    "#         tmp_total = 0\n",
    "#         while right < len(nums):\n",
    "#             tmp_total += nums[right]\n",
    "#             if tmp_total >= k:\n",
    "#                 res = min(right - left+1, res)\n",
    "#                 while left < right:\n",
    "#                     tmp_total -= nums[left]\n",
    "#                     left += 1\n",
    "#                     if tmp_total >= k:\n",
    "#                         res = min(right - left+1, res)\n",
    "#                 if left == right:\n",
    "#                     right += 1\n",
    "#             else:\n",
    "#                 right += 1\n",
    "#         return -1 if res == float('inf') else res\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        if not nums:\n",
    "            return -1\n",
    "\n",
    "        sum_list = [0]\n",
    "        res = float('inf')\n",
    "        for i in range(len(nums)):\n",
    "            sum_list.append(sum_list[-1]+nums[i])\n",
    "\n",
    "        queue = collections.deque()\n",
    "\n",
    "        for i in range(len(sum_list)):\n",
    "            while queue and sum_list[queue[-1]] >= sum_list[i]:\n",
    "                queue.pop()\n",
    "            while queue and (sum_list[i] - sum_list[queue[0]]) >= k:\n",
    "                res = min(res, i - queue[0])\n",
    "                queue.popleft()\n",
    "            queue.append(i)\n",
    "        return -1 if res == float('inf') else res\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    s = Solution()\n",
    "    print(s.shortestSubarray([1], 1))\n",
    "    print(s.shortestSubarray([1, 2], 4))\n",
    "    print(s.shortestSubarray([2, -1, 2], 3))\n",
    "    print(s.shortestSubarray([0, -1, 2], 1))\n",
    "    print(s.shortestSubarray([0, 2, 1], 3))\n",
    "    print(s.shortestSubarray([1, -1, 3, 4], 7))\n",
    "    print(s.shortestSubarray([-28, 81, -20, 28, -29], 89))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        # 这题可以大体套用209的思路。但是由于允许负数，因此需要对负数做特殊处理\n",
    "        min_len = float('inf')\n",
    "\n",
    "        cur_sum = 0\n",
    "        sums = collections.deque([[0, -1]])\n",
    "        for right, num in enumerate(nums):\n",
    "            cur_sum += num\n",
    "            # 遇到负数的话，如果right到负数的和已经>=k的话，那么right到负数右边的和必然也大于k\n",
    "            # 因此可以把小于等于cur_sum的和全部出栈，让sums单调递增。效果等同于用负数右边作为left\n",
    "            while sums and cur_sum <= sums[-1][0]:\n",
    "                sums.pop()\n",
    "            # 双指针不断逼近左右边界。下面就和209完全相同了\n",
    "            while sums and cur_sum - sums[0][0] >= k:\n",
    "                _, left = sums.popleft()\n",
    "                min_len = min(min_len, right - left)\n",
    "            sums.append([cur_sum, right])\n",
    "        return min_len if min_len != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        from bisect import bisect_right\n",
    "\n",
    "        tmp = [(0,-1)]\n",
    "        ans = 0\n",
    "        res = 100000\n",
    "\n",
    "        for idx,n in enumerate(nums):\n",
    "            # print(tmp)\n",
    "            ans+=n \n",
    "            j = bisect_right(tmp,(ans-k,1000000))-1\n",
    "            if j>=0:\n",
    "                res = min(res,idx-tmp[j][1])\n",
    "            while tmp and tmp[-1][0]>=ans:\n",
    "                tmp.pop()\n",
    "            tmp.append((ans,idx))\n",
    "\n",
    "        return res if res<100000 else -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        presum = [0]+nums[:]\n",
    "        for i in range(len(nums)):\n",
    "            presum[i+1] += presum[i]\n",
    "        \n",
    "        que = deque() #单调递增队列\n",
    "        result = len(nums)+1\n",
    "        for i,n in enumerate(presum):\n",
    "            while que and que[-1][0] >= n: #保持单调性\n",
    "                que.pop()\n",
    "            while que and n - que[0][0] >= k: #队列够长了\n",
    "                result = min(result,i-que[0][1])\n",
    "                que.popleft()\n",
    "            que.append([n,i])\n",
    "\n",
    "        return result if result <= len(nums) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        pre = list(accumulate([0]+nums))\n",
    "        res, A = float('inf'), []\n",
    "        for j, val in enumerate(pre):\n",
    "            while A and A[-1][0]>=val:\n",
    "                A.pop()\n",
    "            pos = bisect_right(A, (val-k, float('inf')))-1\n",
    "            if pos >= 0:\n",
    "                res = min(res, j-A[pos][1])\n",
    "            A.append((val, j))\n",
    "        return res if res < float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def binarysearch(self, n, l, r, x):\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) >> 1\n",
    "            if n[mid][0] <= x: l = mid\n",
    "            else: r = mid - 1\n",
    "             \n",
    "        if n[l][0] > x:\n",
    "            l = -1\n",
    "        return l\n",
    "    \n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        # 构建前缀和\n",
    "        nums = [0] + nums\n",
    "        s = [0 for _ in range(len(nums))]\n",
    "        for i in range(1, len(nums)):\n",
    "            s[i] = s[i - 1] + nums[i]\n",
    "        \n",
    "        min_length = float('inf')\n",
    "        stack = [[0, 0]]\n",
    "        # 遍历nums\n",
    "        for i in range(1, len(nums)):\n",
    "            # 构建到i之前的单调栈\n",
    "            while stack and stack[-1][0] > s[i]:\n",
    "                stack.pop(-1)\n",
    "            stack.append([s[i], i])\n",
    "            \n",
    "            max_s_idx = self.binarysearch(stack, 0, len(stack) - 1, s[i] - k) \n",
    "            if max_s_idx == -1:\n",
    "                continue\n",
    "            else:\n",
    "                min_length = min(min_length, i - stack[max_s_idx][1])\n",
    "            \n",
    "        min_length = -1 if min_length == float('inf')  else min_length\n",
    "        return min_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        leng=len(nums)\n",
    "        # if sum(nums)<k:\n",
    "        #     return -1\n",
    "        res=leng+1\n",
    "        cur=0\n",
    "        presum=[]\n",
    "\n",
    "        from heapq import heappop,heappush\n",
    "\n",
    "        heappush(presum,[0,0])\n",
    "        for i in range(1,leng+1):\n",
    "            cur+=nums[i-1]\n",
    "            # presum[i]+=cur\n",
    "\n",
    "            heappush(presum,[cur,i])\n",
    "            \n",
    "            j=0\n",
    "            while len(presum)>0:\n",
    "                vcur,vi=heappop(presum)\n",
    "                #print(vi,cur,cur-vcur)\n",
    "                if cur-vcur>=k:\n",
    "                    res=min(res,i-vi)\n",
    "                else:\n",
    "                    heappush(presum,[vcur,vi])\n",
    "                    break\n",
    "\n",
    "\n",
    "             \n",
    "        return res if res<leng+1 else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, A: List[int], K: int) -> int:\n",
    "        from collections import deque\n",
    "        t = {-1: 0}\n",
    "        q = deque()\n",
    "        q.append(-1)\n",
    "        pre = 0\n",
    "        res = len(A) + 1\n",
    "        for i, x in enumerate(A):\n",
    "            pre += x\n",
    "            t[i] = pre\n",
    "            while q and t[q[-1]] >= pre:\n",
    "                q.pop()\n",
    "            while q and pre - t[q[0]] >= K:\n",
    "                res = min(res, i - q.popleft())\n",
    "            q.append(i)\n",
    "        return res if res < len(A) + 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        prefix = [(-1, 0)]\n",
    "        for i in range(len(nums)):\n",
    "            prefix.append((i, prefix[i][1] + nums[i]))\n",
    "        \n",
    "        queue = []\n",
    "        length = 50003\n",
    "        for i in prefix:\n",
    "            while queue and i[1] <= queue[-1][1]:\n",
    "                queue.pop()\n",
    "            while queue and i[1] - queue[0][1] >= k:\n",
    "                length = min(length, i[0] - queue[0][0])\n",
    "                queue.pop(0)\n",
    "            queue.append(i)\n",
    "\n",
    "        return -1 if length == 50003 else length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        length = len(nums)\n",
    "        sumnum = begin = 0\n",
    "        res = -1\n",
    "        for i in range(length):\n",
    "            if nums[i] >= k:\n",
    "                return 1\n",
    "            sumnum += nums[i]\n",
    "            #贪心\n",
    "            if sumnum < 1:\n",
    "                sumnum = 0\n",
    "                begin = i + 1\n",
    "                continue\n",
    "            j = i - 1\n",
    "            while nums[j + 1] < 0:\n",
    "                nums[j] = nums[j + 1] + nums[j]\n",
    "                nums[j + 1] = 0\n",
    "                j -= 1\n",
    "            if sumnum >= k:\n",
    "                while sumnum - nums[begin] >= k or nums[begin] <= 0:\n",
    "                    sumnum -= nums[begin]\n",
    "                    begin += 1\n",
    "                length = i - begin + 1\n",
    "                if res < 0 or res > length:\n",
    "                    res = length\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        from collections import deque\n",
    "        prefixQueue, idxQueue = deque([0]), deque([-1])\n",
    "        ans, total = -1, 0\n",
    "        for i, num in enumerate(nums):\n",
    "            total += num\n",
    "            while len(prefixQueue) > 0 and prefixQueue[0] <= total - k:\n",
    "                prefixQueue.popleft()\n",
    "                j = idxQueue.popleft()\n",
    "                ans = min(ans, i - j) if ans != -1 else i - j\n",
    "            while len(prefixQueue) > 0 and total <= prefixQueue[-1]:\n",
    "                prefixQueue.pop()\n",
    "                idxQueue.pop()\n",
    "            prefixQueue.append(total)\n",
    "            idxQueue.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        s=list(accumulate(nums,initial=0))\n",
    "        q=deque()\n",
    "        ans=inf\n",
    "        for i,num in enumerate(s):\n",
    "            while q and num-s[q[0]]>=k:\n",
    "                ans=min(ans,i-q.popleft())\n",
    "            while q and num<=s[q[-1]]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return ans if ans<inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        pre = [0] + list(accumulate(nums))\n",
    "        q = deque()\n",
    "        ans = len(nums) + 1\n",
    "\n",
    "        for i in range(len(pre)):\n",
    "            while q and pre[i] - pre[q[0]] >= k:\n",
    "                ans = min(ans, i - q.popleft())\n",
    "            while q and pre[i] <= pre[q[-1]]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return -1 if ans == len(nums) + 1 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        sums = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            sums[i+1] = sums[i] + nums[i]\n",
    "        \n",
    "        min_num = float('inf')\n",
    "        queue = []\n",
    "        for i , curSum in enumerate(sums):\n",
    "            while queue and curSum - sums[queue[0]] >= k:\n",
    "                min_num = min(min_num, i - queue.pop(0)) \n",
    "            while(queue and curSum < sums[queue[-1]]):\n",
    "                queue.pop(-1)\n",
    "            queue.append(i)\n",
    "        return min_num if min_num != float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        prefixSum = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            prefixSum[i] = prefixSum[i - 1] + nums[i - 1]\n",
    "\n",
    "        q = deque([])\n",
    "        ans = n + 1\n",
    "        for idx, val in enumerate(prefixSum):\n",
    "            while q and val - prefixSum[q[0]] >= k:\n",
    "                ans = min(ans, idx - q.popleft())\n",
    "            while q and val <= prefixSum[q[-1]]:\n",
    "                q.pop()\n",
    "            q.append(idx)\n",
    "\n",
    "        return ans if ans < n + 1 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        pre_sum = [0]\n",
    "        for i in nums:\n",
    "            pre_sum.append(pre_sum[-1]+i)\n",
    "        \n",
    "        _min = float('inf')\n",
    "        queue = []\n",
    "        #print(pre_sum)\n",
    "        for index,val in enumerate(pre_sum):\n",
    "            if not queue:\n",
    "                queue.append((val,index))\n",
    "                continue\n",
    "            while queue and val <= queue[-1][0]:\n",
    "                queue.pop(-1)\n",
    "            \n",
    "            while  queue and val - queue[0][0] >= k:\n",
    "                _min = min(_min,index - queue[0][-1])\n",
    "                queue.pop(0)\n",
    "            queue.append((val,index))\n",
    "            #print(index,_min, queue)\n",
    "        if _min < float('inf'):\n",
    "            return _min\n",
    "        else:\n",
    "            return -1 \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        from collections import deque\n",
    "        n = len(nums)\n",
    "        preSum = [0] * (n + 1)\n",
    "        for i in range(1, n+1):\n",
    "            preSum[i] = preSum[i-1] + nums[i-1]\n",
    "        print(preSum)\n",
    "        stack = deque([0])\n",
    "        res = float('inf')\n",
    "        for i in range(1, n+1):\n",
    "            while stack and preSum[i] - preSum[stack[-1]] >= k:\n",
    "                res = min(res, i - stack[-1])\n",
    "                stack.pop()\n",
    "            while stack and preSum[i] - preSum[stack[0]] >= k:\n",
    "                res = min(res, i - stack[0])\n",
    "                stack.popleft()\n",
    "            while stack and preSum[i] <= preSum[stack[-1]]:\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return res if res != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], target: int) -> int:\n",
    "        totalStack, idxStack = [0], [-1]\n",
    "        ans, total = -1, 0\n",
    "        for i, num in enumerate(nums):\n",
    "            total += num\n",
    "            if len(totalStack) > 0 and totalStack[0] <= total - target:\n",
    "                l, r = 0, len(totalStack) - 1\n",
    "                while l < r:  # 二分查找 idx，满足 maxStack[l] <= total - target 的情况下，idx 越大越好\n",
    "                    m = (l + r + 1) >> 1\n",
    "                    if totalStack[m] <= total - target:\n",
    "                        l = m\n",
    "                    else:\n",
    "                        r = m - 1\n",
    "                ans = min(ans, i - idxStack[l]) if ans != -1 else i - idxStack[l]\n",
    "            while len(totalStack) > 0 and total < totalStack[-1]:\n",
    "                totalStack.pop()\n",
    "                idxStack.pop()\n",
    "            totalStack.append(total)\n",
    "            idxStack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        prefixStack, idxStack = [0], [-1]\n",
    "        ans, total = -1, 0\n",
    "        for i, num in enumerate(nums):\n",
    "            total += num\n",
    "            # 前缀和单调栈 [-1, 0, 1, 4]\n",
    "            # total - x >= k => x <= total - k\n",
    "            if len(prefixStack) > 0 and prefixStack[0] <= total - k:  # 至少栈低元素是满足的\n",
    "                l, r = 0, len(prefixStack) - 1  # 查找满足条件时更大的idx\n",
    "                while l < r:\n",
    "                    m = (l + r + 1) >> 1\n",
    "                    if prefixStack[m] <= total - k:\n",
    "                        l = m\n",
    "                    else:\n",
    "                        r = m - 1\n",
    "                ans = min(ans, i - idxStack[l]) if ans != -1 else i - idxStack[l]\n",
    "            while len(prefixStack) > 0 and prefixStack[-1] >= total:\n",
    "                prefixStack.pop()\n",
    "                idxStack.pop()\n",
    "            prefixStack.append(total)\n",
    "            idxStack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        ans = inf\n",
    "        cur_s = 0\n",
    "        q = deque([(0, -1)])\n",
    "        for i, x in enumerate(nums):\n",
    "            cur_s += x  # 计算前缀和\n",
    "            while q and cur_s - q[0][0] >= k:\n",
    "                ans = min(ans, i - q.popleft()[1])  # 优化一\n",
    "            while q and q[-1][0] >= cur_s:\n",
    "                q.pop()  # 优化二\n",
    "            q.append((cur_s, i))\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        d = deque([(0, -1), ])\n",
    "        n = len(nums)\n",
    "        res = float('inf')\n",
    "        cur = 0\n",
    "        for i in range(n):\n",
    "            cur += nums[i]\n",
    "            while d and cur - d[0][0] >= k:\n",
    "                res = min(res, i-d.popleft()[1])\n",
    "            while d and cur <= d[-1][0]:\n",
    "                d.pop()\n",
    "            d.append([cur, i])\n",
    "        return res if res != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        q = collections.deque([[0, 0]])\n",
    "        acc = 0\n",
    "        res = float('inf')\n",
    "        for i, n in enumerate(nums, 1):\n",
    "            acc += n\n",
    "            while q and acc-q[0][0]>=k:\n",
    "                res = min(res, i-q.popleft()[1])\n",
    "\n",
    "            while q and q[-1][0]>=acc:\n",
    "                q.pop()\n",
    "\n",
    "            q.append([acc, i])\n",
    "\n",
    "        return res if res<float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        q = deque([[-1, 0]]) # index, value \n",
    "        sum = 0\n",
    "        ans = inf \n",
    "        for i, v in enumerate(nums):\n",
    "            sum += v \n",
    "            \n",
    "            # 入\n",
    "            while q and sum <= q[-1][1]:\n",
    "                q.pop()\n",
    "            q.append([i, sum])\n",
    "\n",
    "            # 出 \n",
    "            while q and q[-1][1] - q[0][1] >= k:\n",
    "                ans = min(ans, q[-1][0]-q[0][0])\n",
    "                q.popleft()\n",
    "        return -1 if ans == inf else ans \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        #算出累积和\n",
    "        n=len(nums)\n",
    "        presum = [0] + list(accumulate(nums))\n",
    "        res=n+1\n",
    "        dq=deque()\n",
    "#以当前位置为子数组的右侧，左侧从前缀和最小开始试。每次尝试都在缩减区间。每次右侧向右一步，左侧在之前的基础上向右侧靠近\n",
    "        for i in range(n+1):\n",
    "            cur_presum=presum[i]\n",
    "            # 如果有能符合条件的，那么肯定是deque中第一个和最后一个\n",
    "            # 如果符合就把第一个扔掉，找到第一个不符合的，那么就是距离最近的\n",
    "            while dq and cur_presum-presum[dq[0]]>=k:\n",
    "                res=min(res, i-dq.popleft())\n",
    "            # 将deque末尾比curSum大的值都pop，保持递增的deque\n",
    "            # 前面的sum都被curSum小，才能保证将sum_i有的比\n",
    "            while dq and cur_presum <= presum[dq[-1]]:\n",
    "                dq.pop()\n",
    "            dq.append(i)\n",
    "        if res == n+1:\n",
    "            return -1\n",
    "        else:\n",
    "            return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        res = inf\n",
    "        q = deque()\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        for i, x in enumerate(s):\n",
    "            while q and x - s[q[0]] >= k:\n",
    "                res = min(res, i - q.popleft())\n",
    "            while q and s[q[-1]] >= x:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return res if res != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 看题目的数据范围，前缀和数组中元素可能非常大，所以用 long 类型\n",
    "        preSumArr = [0] * (n + 1)\n",
    "        # 计算 nums 的前缀和数组\n",
    "        for i in range(1, n + 1):\n",
    "            preSumArr[i] = preSumArr[i - 1] + nums[i - 1]\n",
    "        q = list()\n",
    "        res = float(\"inf\")\n",
    "        # 开始执行滑动窗口算法框架\n",
    "        for i, curSum in enumerate(preSumArr):\n",
    "            while q and curSum - preSumArr[q[0]] >= k:\n",
    "                res = min(res, i - q.pop(0))\n",
    "            while q and preSumArr[q[-1]] >= curSum:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "\n",
    "\n",
    "        return res if res != float(\"inf\") else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        pre_sum = list(accumulate(nums, initial=0))\n",
    "        q, ans = deque(), inf\n",
    "        for i, s in enumerate(pre_sum):\n",
    "            while q and s - q[0][1] >= k:\n",
    "                j, _ = q.popleft()\n",
    "                ans = min(ans, i - j)\n",
    "            while q and s <= q[-1][1]:\n",
    "                q.pop()\n",
    "            q.append((i, s))\n",
    "        return ans if ans < inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        i, total, ans = 0, 0, float('inf')\n",
    "        h = [(0, -1)]\n",
    "        while i < len(nums):\n",
    "            total = total + nums[i]\n",
    "            while h and total - h[0][0] >= k:\n",
    "                _total, j = heapq.heappop(h)\n",
    "                ans = min(i - j, ans)\n",
    "\n",
    "            heapq.heappush(h, (total, i))\n",
    "            i += 1\n",
    "\n",
    "        return ans if ans != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = [0]*(n+1)\n",
    "        s[0] = 0\n",
    "        for i in range(n):\n",
    "            s[i+1] = s[i] + nums[i]\n",
    "\n",
    "        minn = n+1\n",
    "        deque = [0]*100001\n",
    "        l = 0\n",
    "        r = 0\n",
    "        for i in range(len(s)):\n",
    "            while r > l and s[deque[r-1]] >= s[i]:\n",
    "                r -= 1\n",
    "            while r > l and s[i] - s[deque[l]] >= k:\n",
    "                minn = min(minn, i-deque[l])\n",
    "                l += 1\n",
    "            deque[r] = i\n",
    "            r += 1\n",
    "        return minn if minn <= n else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int: \n",
    "        pre_sum = 0 # index, val\n",
    "        import bisect\n",
    "        l = len(nums)\n",
    "        if l == 1:\n",
    "            return 1 if nums[0] >=k else -1\n",
    "        inf = 2 ** 31\n",
    "        mono_stack = []\n",
    "        pos = []\n",
    "        res = inf\n",
    "        for i,x in enumerate(nums):\n",
    "            pre_sum += x\n",
    "            if pre_sum>=k:res = min(res,i+1)\n",
    "            tar = pre_sum-k\n",
    "            if mono_stack and mono_stack[0]<=tar:\n",
    "                index = -4\n",
    "                if mono_stack[-1]<= tar:\n",
    "                    index = pos[-1]\n",
    "                else:\n",
    "                    index = pos[bisect.bisect(mono_stack,tar)-1]\n",
    "                # print(tar,mono_stack,index)\n",
    "                res = min(res,i-index)\n",
    "            while mono_stack and pre_sum <= mono_stack[-1]:\n",
    "                mono_stack.pop()\n",
    "                pos.pop()\n",
    "            mono_stack.append(pre_sum)\n",
    "            pos.append(i)\n",
    "        return res if res != inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre_sum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            pre_sum[i + 1] = pre_sum[i] + nums[i]\n",
    "        queue = []\n",
    "        ans = inf\n",
    "        for i in range(n + 1):\n",
    "            x = pre_sum[i]\n",
    "            if not queue:\n",
    "                queue.append(i)\n",
    "            else:\n",
    "                while queue and x <= pre_sum[queue[-1]]:\n",
    "                    queue.pop()\n",
    "                if not queue or x - pre_sum[queue[0]] < k:\n",
    "                    queue.append(i)\n",
    "                    continue\n",
    "                j = bisect_left(queue, x - k, key = lambda x: pre_sum[x])\n",
    "                if j == len(queue):\n",
    "                    j -= 1\n",
    "                elif pre_sum[queue[j]] > x - k and j > 0:\n",
    "                    j = j - 1\n",
    "                ans = min(ans, i - queue[j])\n",
    "                queue.append(i)\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heappop\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        s = [0]\n",
    "        su = 0\n",
    "        for num in nums:\n",
    "            su += num\n",
    "            s.append(su)\n",
    "\n",
    "        min_l = 1000000\n",
    "        heap_array = []\n",
    "        for i, num in enumerate(s):\n",
    "            if len(heap_array) == 0:\n",
    "                heap_array.append((num, i))\n",
    "                continue\n",
    "            while len(heap_array) > 0:\n",
    "                top_num = heap_array[0][0]\n",
    "                top_id = heap_array[0][1]\n",
    "                if num-top_num >= k:\n",
    "                    min_l = min(min_l, i-top_id)\n",
    "                    heappop(heap_array)\n",
    "                else:\n",
    "                    break\n",
    "            heappush(heap_array, (num, i))\n",
    "\n",
    "        return -1 if min_l == 1000000 else min_l\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        queue = [[0,-1]]\n",
    "        total = 0\n",
    "        ans = inf\n",
    "        for i,j in enumerate(nums):\n",
    "            total += j\n",
    "            while queue and total-k >= queue[0][0]:\n",
    "                ans = min(ans,i-heappop(queue)[-1])\n",
    "            heappush(queue,[total,i])\n",
    "        return ans if ans != inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        pre = list(itertools.accumulate(nums, initial=0))\n",
    "        h = []\n",
    "        ans = math.inf\n",
    "        for i,v in enumerate(nums):\n",
    "            heapq.heappush(h, (pre[i], i))\n",
    "            while h and h[0][0] <= pre[i+1]-k:\n",
    "                _, j = heapq.heappop(h)\n",
    "                ans = min(ans, i+1-j)\n",
    "        return ans if ans < math.inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        preSum = [0]\n",
    "        tinydict = dict()\n",
    "        tinydict[0] = 0\n",
    "        i = l = r = 0\n",
    "        res = len(nums)+1\n",
    "\n",
    "        for num in nums:\n",
    "            i += 1\n",
    "            val = preSum[-1]+num\n",
    "            while preSum and val < preSum[-1] : \n",
    "                preSum.pop()\n",
    "            \n",
    "            while r < len(preSum) and val - preSum[r] >= k :\n",
    "                res = min(res,i - tinydict[preSum[r]])\n",
    "                r += 1\n",
    "\n",
    "            tinydict[val] = i\n",
    "            preSum.append(val)\n",
    "        \n",
    "\n",
    "        return -1 if res == len(nums)+1 else res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        total = 0\n",
    "        asc_stack: deque = deque([-1])\n",
    "        prefix_sum: Dict[int, int] = {-1: 0}\n",
    "        result = math.inf\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            total += nums[i]\n",
    "            prefix_sum[i] = total\n",
    "\n",
    "            while asc_stack and total - prefix_sum[asc_stack[0]] >= k:\n",
    "                # (asc_stack[0], i] subarray has sum >= k\n",
    "                result = min(result, i-asc_stack[0])\n",
    "                asc_stack.popleft()\n",
    "            \n",
    "            while asc_stack and total <= prefix_sum[asc_stack[-1]]:\n",
    "                asc_stack.pop()\n",
    "            asc_stack.append(i)\n",
    "        \n",
    "        return -1 if result == math.inf else result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        total = 0\n",
    "        asc_stack: deque = deque([-1])\n",
    "        prefix_sum: Dict[int, int] = {-1: 0}\n",
    "        result = math.inf\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            total += nums[i]\n",
    "            prefix_sum[i] = total\n",
    "\n",
    "            while asc_stack and total - prefix_sum[asc_stack[0]] >= k:\n",
    "                # (asc_stack[0], i] subarray has sum >= k\n",
    "                result = min(result, i-asc_stack[0])\n",
    "                asc_stack.popleft()\n",
    "            \n",
    "            while asc_stack and total <= prefix_sum[asc_stack[-1]]:\n",
    "                asc_stack.pop()\n",
    "            asc_stack.append(i)\n",
    "\n",
    "            # print(f\"after putting {i}, deque is: {asc_stack}\")\n",
    "        \n",
    "        return -1 if result == math.inf else result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        ns = [i for i in accumulate(nums, initial=0)]\n",
    "        # print(ns)\n",
    "        q = deque()\n",
    "        q.append(0)\n",
    "        dd = {}\n",
    "        dd[ns[0]] = 0\n",
    "        r = 10**9\n",
    "        for i in range(1,len(ns)):\n",
    "            while q and ns[i]-q[0]>=k:\n",
    "                r = min(r, i-dd[q[0]])\n",
    "                q.popleft()\n",
    "            while q and ns[i]<=q[-1]:\n",
    "                q.pop()\n",
    "            q.append(ns[i])\n",
    "            dd[ns[i]] = i\n",
    "\n",
    "        if r==10**9:\n",
    "            return -1\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "        时间复杂度：O(n)，其中 n 是数组 nums 的长度。求【前缀和数组】消耗 O(n)。preSumArr 每个下标会入 q 一次，最多出 q 一次。\n",
    "        空间复杂度：O(n)。preSumArr 和 q 长度均为 O(n)\n",
    "        \"\"\"\n",
    "\n",
    "        # pre_sum_arr = [0]  # 前缀和数组，首元素为0，作为边界元素\n",
    "        # for i in range(len(nums)):\n",
    "        #     pre_sum_arr.append(pre_sum_arr[-1] + nums[i])\n",
    "        #\n",
    "        # ans = inf\n",
    "        # q = deque()  # 双端队列\n",
    "        # for i, curr_sum in enumerate(pre_sum_arr):\n",
    "        #     # 现在的前缀和 - 队列首部的前缀和 >= k时，就更新结果，并弹出队列首部的元素\n",
    "        #     while q and curr_sum - pre_sum_arr[q[0]] >= k:  # 优化一\n",
    "        #         ans = min(ans, i - q.popleft())\n",
    "        #\n",
    "        #     # 现在的前缀和 <= 队列尾部的前缀和时，弹出队尾的元素\n",
    "        #     while q and pre_sum_arr[q[-1]] >= curr_sum:  # 优化二\n",
    "        #         q.pop()\n",
    "        #\n",
    "        #     # 当前位置的[前缀和]进入数组\n",
    "        #     q.append(i)\n",
    "        # return ans if ans < inf else -1\n",
    "\n",
    "        # ans = inf  # 初始化为较大值\n",
    "        # curr_sum = 0\n",
    "        # q = deque([(0, -1)])  # 添加前置项（前缀和，索引）\n",
    "        #\n",
    "        # for i, x in enumerate(nums):\n",
    "        #     curr_sum += x  # 计算前缀和\n",
    "        #     while q and curr_sum - q[0][0] >= k:  # 优化一\n",
    "        #         ans = min(ans, i - q.popleft()[1])\n",
    "        #\n",
    "        #     while q and q[-1][0] >= curr_sum:  # 优化二\n",
    "        #         q.pop()\n",
    "        #\n",
    "        #     q.append((curr_sum, i))  # (前缀和, 索引)\n",
    "        # return ans if ans < inf else -1\n",
    "\n",
    "        def binarySearch(arr, target):\n",
    "            # arr[:l] <= target\n",
    "            l, r = 0, len(arr)\n",
    "            while l < r:\n",
    "                mid = (l + r) >> 1\n",
    "                if arr[mid][0] > target:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return l\n",
    "\n",
    "        # 时间复杂度为O(nlogn)，空间复杂度为O(n)\n",
    "        stack = [(0, -1)]  # 前缀和单调递增栈，栈中元素为（前缀和，对应数组索引）\n",
    "        window_sum = 0\n",
    "        min_len = inf\n",
    "        for right, num in enumerate(nums):\n",
    "            window_sum += num\n",
    "\n",
    "            while stack and stack[-1][0] >= window_sum:\n",
    "                stack.pop()\n",
    "\n",
    "            idx = binarySearch(stack, window_sum - k)\n",
    "            if idx > 0:\n",
    "                min_len = min(min_len, right - stack[idx - 1][1])\n",
    "\n",
    "            stack.append((window_sum, right))\n",
    "        return min_len if min_len < inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.que = deque()\n",
    "        self.prefix_addition = []\n",
    "\n",
    "    def print_result(self, ret: int) -> int:\n",
    "        return -1 if ret == 100000000 else ret\n",
    "\n",
    "    def bisect_right(self, x: int) -> int:\n",
    "        if len(self.que) == 0:\n",
    "            return -10\n",
    "        l, r = 0, len(self.que) - 1\n",
    "        mid = (l + r) // 2\n",
    "        ret = -10\n",
    "        while l <= r:\n",
    "            if self.que[mid][0] <= x:\n",
    "                ret = self.que[mid][1]\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "            mid = (l + r) // 2\n",
    "        return ret\n",
    "\n",
    "    def add_element(self, x: int, idx: int) -> None:\n",
    "        while len(self.que) != 0 and x <= self.que[len(self.que)-1][0]:\n",
    "            self.que.pop()\n",
    "        self.que.append([x, idx])\n",
    "\n",
    "    def shortestSubarray(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return -1\n",
    "        ret = 100000000\n",
    "        self.prefix_addition.append(nums[0])\n",
    "        for i in range(1, len(nums)):\n",
    "            self.prefix_addition.append(nums[i] + self.prefix_addition[i - 1])\n",
    "        self.que.append([0, -1])\n",
    "        for i in range(len(self.prefix_addition)):\n",
    "            idx_l = self.bisect_right(self.prefix_addition[i] - k)\n",
    "            if idx_l != -10:\n",
    "                ret = min([ret, i - idx_l])\n",
    "            self.add_element(self.prefix_addition[i], i)\n",
    "        return self.print_result(ret)\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    so = Solution()\n",
    "    print(so.shortestSubarray([2, -1, 2], 3))\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
